//给你一个长度为 n 的整数数组 nums 和 一个目标值 target。请你从 nums 中选出三个整数，使它们的和与 target 最接近。 
//
// 返回这三个数的和。 
//
// 假定每组输入只存在恰好一个解。 
//
// 
//
// 示例 1： 
//
// 
//输入：nums = [-1,2,1,-4], target = 1
//输出：2
//解释：与 target 最接近的和是 2 (-1 + 2 + 1 = 2) 。
// 
//
// 示例 2： 
//
// 
//输入：nums = [0,0,0], target = 1
//输出：0
// 
//
// 
//
// 提示： 
//
// 
// 3 <= nums.length <= 1000 
// -1000 <= nums[i] <= 1000 
// -104 <= target <= 104 
// 
// Related Topics 数组 双指针 排序 
// 👍 1152 👎 0


package com.cjl.leetcode.editor.cn;

import java.util.Arrays;

/**
 * [P16]_最接近的三数之和
 * @author cjl
 * @date 2022-05-29 13:12:45
 */
public class P16_ThreeSumClosest{
      public static void main(String[] args) {
            //测试代码
           Solution solution = new P16_ThreeSumClosest().new Solution();
          System.out.println("args = " + solution.threeSumClosest(new int[]{-1,2,1,-4},1));
      }
      //力扣代码
      //leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public int threeSumClosest(int[] nums, int target) {
        /**
         * 解题思路： P15变种
         *  方案一：重排序，三重遍历，计算和并与target比较，选取最接近的； 时间复杂度O(n^3)
         *  方案二：重排期，遍历+双指针， 时间复杂度O(n^2)
         *  双指针：随着第一个元素的递增，第二个元素是递减的，那么就可以使用双指针的方法，将枚举的时间复杂度从 O(N^2) 减少至 O(N)
         */
        int res =Integer.MAX_VALUE;
        Arrays.sort(nums);
        for(int i =0 ; i < nums.length; i++){
            for(int j = i+1, k = nums.length -1; j< k;){
                int tmp = nums[i] + nums[j] + nums[k];
                if(tmp == target){
                    return target;
                }else if( tmp> target){
                    k--;
                }else if(tmp < target){
                    j++;
                }
                if(Math.abs(tmp -target) < Math.abs(res)){
                    res = tmp -target;
                }
            }
        }
        return res + target;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

  }